# -*- coding: UTF-8 -*-
"""
@author:tgy
@file:_01_背包问题.py
@time:2021/01/04
"""


def knapsack(weights, values, bag):
    ...
    if not len(weights) or bag <= 0:
        return 0
    return find_max_value(weights, values, bag, 0)


def find_max_value(weights, values, last, index):
    """
    :param weights: 总量
    :param values: 质量
    :param last: 剩余可以装
    :param index: 装袋的索引
    :return: 最大价值
    """
    if index >= len(weights):
        return 0

    # 不装index
    no_add = find_max_value(weights, values, last, index + 1)

    max_val = no_add
    add_bag = -1
    # 装 index
    if last >= weights[index]:
        add_bag = find_max_value(weights, values, last - weights[index], index + 1) + values[index]
        max_val = max(max_val, add_bag)

    print(f'weights:{weights}, values:{values},bag:{bag}')
    val_message = f'index = {index}\t,weight:{weights[index]}\t,value:{values[index]}\t,last:{last}\t,no_add:{no_add}\t,add_bag:{add_bag}\t,max_val:{max_val}'
    print(val_message, end='\n\n')

    return max_val


def knapsack_matrix(weights, values, bag):
    """
    dp[i] = max(dp[i - 1],dp[i-1]+values[i])

    10
        6 5 4 6 3
    2 0 6
    6
    5
    4
    2
    dp(i,j) 把前i件物品放入容量为j的包中

    dp = max(dp[i-1,j],d[i-1,j - weight[i]] + values[i])

    """
    dp = [0] * (bag + 1)

    for i in range(1, len(weights)+ 1):
        ...
        for j in range(bag, -1, -1):
            ...
            if j >= weights[i - 1]:
                dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])
        print(dp)


if __name__ == '__main__':
    pass
    weights = [2, 6, 5, 4, 2]
    values = [6, 5, 4, 6, 3]
    bag = 10
    # print(f'weights:{weights}, values:{values},bag:{bag}')
    # max = knapsack(weights, values, bag)
    max = knapsack_matrix(weights, values, bag)
    print(max)
